Search for: All records

We build the first sub-linear (in fact, potentially constant-time) public-key searchable encryption system: server can publish a public key PK. anybody can build an encrypted index for document D under PK. client holding the index can obtain a token 𝑧𝑤 from the server to check if a keyword w belongs to D. search using 𝑧𝑤 is almost as fast (e.g., sub-linear) as the non-private search. server granting the token does not learn anything about the document D, beyond the keyword w. yet, the token 𝑧𝑤 is specific to the pair (D, w): the client does not learn if other keywords 𝑤′≠𝑤 belong to D, or if w belongs to other, freshly indexed documents 𝐷′. server cannot fool the client by giving a wrong token 𝑧𝑤. We call such a primitive Encapsulated Search Index (ESI). Our ESI scheme can be made (t, n)-distributed among n servers in the best possible way: non-interactive, verifiable, and resilient to any coalition of up to (𝑡−1) malicious servers. We also introduce the notion of delegatable ESI and show how to extend our construction to this setting. Our solution — including public indexing, sub-linear search, delegation, and distributed token generation — is deployed as a commercial application by a real-world company.